#include <iostream>
#include <string>
#include <vector>
#include <thread>
#include <chrono>
#include <atomic>
#include <iomanip>
#include "Hash_LRU_K.h"
#include <random>
#include <climits>

using namespace std;

void runTest(const string& testName, bool result) {
    cout << testName << ": " << (result ? "PASS" : "FAIL") << endl;
}

// 测试1: 基础功能测试
void testBasicFunctionality() {
    cout << "=== 测试1: 基础功能测试 ===" << endl;
    
    HashLruKCaches<int, string> cache(100, 4, 2); // 总容量100，4个分片，K=2
    string value;
    bool result = true;
    
    // 基础put/get
    cache.put(1, "one");
    result &= cache.get(1, value) && value == "one";
    
    // 测试不同分片
    cache.put(2, "two");
    cache.put(100, "hundred"); // 应该在不同分片
    result &= cache.get(2, value) && value == "two";
    result &= cache.get(100, value) && value == "hundred";
    
    // 测试LRU-K晋升机制
    cache.put(3, "three");
    cache.get(3, value); // put+get达到K=2，应该晋升
    // 再次访问应该命中
    result &= cache.get(3, value) && value == "three";
    
    runTest("基础功能", result);
}

// 测试2: 分片分布测试
void testShardDistribution() {
    cout << "\n=== 测试2: 分片分布测试 ===" << endl;
    
    HashLruKCaches<int, int> cache(100, 5, 2); // 5个分片
    bool result = true;
    
    // 插入大量数据，验证分布均匀性
    const int testSize = 1000;
    vector<int> shardHits(5, 0);
    
    for (int i = 0; i < testSize; ++i) {
        cache.put(i, i * 10);
        int value;
        if (cache.get(i, value)) {
            // 通过哈希计算确定分片（简化版本，实际需要访问内部状态）
            size_t shardIndex = hash<int>{}(i) % 5;
            shardHits[shardIndex]++;
        }
    }
    
    // 检查每个分片都有数据
    for (int hits : shardHits) {
        result &= (hits > 0);
        cout << "分片数据量: " << hits << endl;
    }
    
    runTest("分片分布", result);
}

// 测试3: 容量限制测试
void testCapacityLimit() {
    cout << "\n=== 测试3: 容量限制测试 ===" << endl;
    
    HashLruKCaches<int, int> cache(20, 4, 2); // 总容量20，4个分片（每个分片约5个元素）
    bool result = true;
    
    // 插入超过容量的数据
    for (int i = 0; i < 50; ++i) {
        cache.put(i, i * 10);
    }
    
    // 验证最早的数据被淘汰
    int value;
    result &= !cache.get(0, value);  // 早期数据应该被淘汰
    result &= !cache.get(10, value); // 部分数据被淘汰
    
    // 但最近的数据应该还在
    result &= cache.get(49, value) && value == 490;
    
    runTest("容量限制", result);
}

// 测试4: 淘汰策略测试
// 测试4: 精确的淘汰策略测试
void testPreciseEvictionPolicy() {
    cout << "\n=== 测试4: 精确淘汰策略测试 ===" << endl;
    
    // 使用更小的容量来确保触发淘汰
    HashLruKCaches<int, string> cache(6, 2, 2); // 总容量6，2个分片（每个分片3个主元素）
    bool result = true;
    string value;
    
    // 首先确定哪些key会哈希到不同分片
    vector<int> shard0Keys, shard1Keys;
    hash<int> hashFunc;
    
    // 寻找哈希到不同分片的key
    for (int key = 1; key <= 100; key++) {
        if (shard0Keys.size() < 7 && shard1Keys.size() < 7) {
            if (hashFunc(key) % 2 == 0) {
                shard0Keys.push_back(key);
            } else {
                shard1Keys.push_back(key);
            }
        } else {
            break;
        }
    }
    
    cout << "分片0的测试key: ";
    for (int k : shard0Keys) cout << k << " ";
    cout << endl;
    cout << "分片1的测试key: ";
    for (int k : shard1Keys) cout << k << " ";
    cout << endl;
    
    // 测试分片0的淘汰
    cout << "\n测试分片0的淘汰:" << endl;
    for (int i = 0; i < shard0Keys.size(); i++) {
        cache.put(shard0Keys[i], "value_" + to_string(shard0Keys[i]));
        cache.get(shard0Keys[i], value);  // 晋升到主缓存
        cout << "插入 key=" << shard0Keys[i] << "到主缓存" << endl;
    }
    
    // 验证分片0的淘汰
    int missingInShard0 = 0;
    for (int i = 0; i < shard0Keys.size(); ++i) {
        int key = shard0Keys[i];
        if (!cache.get(key, value)) {
            missingInShard0++;
            cout << "key=" << key << " 已被淘汰" << endl;
        }
    }
    cout << "分片0被淘汰数量: " << missingInShard0 << endl;
    result &= (missingInShard0 > 0);
    
    // 测试分片1的淘汰
    cout << "\n测试分片1的淘汰:" << endl;
    for (int i = 0; i < shard1Keys.size(); ++i) {
        cache.put(shard1Keys[i], "value_" + to_string(shard1Keys[i]));
        cache.get(shard1Keys[i], value);  // 晋升到主缓存
        cout << "插入 key=" << shard1Keys[i] << "到主缓存" << endl;
    }
    
    // 验证分片1的淘汰
    int missingInShard1 = 0;
    for (int i = 0; i < shard1Keys.size(); ++i) {
        int key = shard1Keys[i];
        if (!cache.get(key, value)) {
            missingInShard1++;
            cout << "key=" << key << " 已被淘汰" << endl;
        }
    }
    cout << "分片1被淘汰数量: " << missingInShard1 << endl;
    result &= (missingInShard1 > 0);
    
    runTest("精确淘汰策略", result);
}

// 测试5: 并发读写测试
void testConcurrentAccess() {
    cout << "\n=== 测试5: 并发读写测试 ===" << endl;
    
    HashLruKCaches<int, int> cache(1000, 8, 2); // 8个分片提高并发性
    const int threadCount = 8;
    const int operationsPerThread = 1000;
    atomic<int> totalHits(0);
    atomic<int> totalOperations(0);
    
    auto worker = [&](int threadId) {
        int hits = 0;
        for (int i = 0; i < operationsPerThread; ++i) {
            int key = (threadId * operationsPerThread + i) % 500; // 有限key范围产生冲突
            int value;
            
            if (i % 3 == 0) {
                // 写操作
                cache.put(key, threadId * 1000 + i);
            } else {
                // 读操作
                if (cache.get(key, value)) {
                    hits++;
                }
            }
        }
        totalHits += hits;
        totalOperations += operationsPerThread;
    };
    
    vector<thread> threads;
    auto startTime = chrono::high_resolution_clock::now();
    
    // 启动多个线程
    for (int i = 0; i < threadCount; ++i) {
        threads.emplace_back(worker, i);
    }
    
    // 等待所有线程完成
    for (auto& t : threads) {
        t.join();
    }
    
    auto endTime = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
    
    double hitRate = static_cast<double>(totalHits) / (totalOperations * 2.0 / 3.0) * 100; // 只计算读操作
    
    cout << "线程数: " << threadCount << endl;
    cout << "总操作数: " << totalOperations << endl;
    cout << "命中次数: " << totalHits << endl;
    cout << "命中率: " << fixed << setprecision(2) << hitRate << "%" << endl;
    cout << "总耗时: " << duration.count() << "ms" << endl;
    
    runTest("并发访问", true);
}

// 测试6: 高并发压力测试
void testHighConcurrencyStress() {
    cout << "\n=== 测试6: 高并发压力测试 ===" << endl;
    
    HashLruKCaches<int, string> cache(5000, 16, 2); // 大容量，多分片
    const int threadCount = 16;
    const int operationsPerThread = 5000;
    atomic<long> totalSuccess(0);
    
    auto stressWorker = [&](int threadId) {
        long success = 0;
        for (int i = 0; i < operationsPerThread; ++i) {
            int key = (threadId * 131 + i * 37) % 2000; // 伪随机分布
            string value;
            
            if (cache.get(key, value)) {
                success++;
            } else {
                cache.put(key, "data_" + to_string(threadId) + "_" + to_string(i));
                success++;
            }
        }
        totalSuccess += success;
    };
    
    vector<thread> threads;
    auto startTime = chrono::high_resolution_clock::now();
    
    // 预热缓存
    for (int i = 0; i < 1000; ++i) {
        cache.put(i, "warmup_" + to_string(i));
    }
    
    // 启动压力测试线程
    for (int i = 0; i < threadCount; ++i) {
        threads.emplace_back(stressWorker, i);
    }
    
    for (auto& t : threads) {
        t.join();
    }
    
    auto endTime = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime);
    
    cout << "压力测试完成" << endl;
    cout << "总成功操作: " << totalSuccess << endl;
    cout << "吞吐量: " << fixed << setprecision(2) 
         << (totalSuccess * 1000.0 / duration.count()) << " ops/sec" << endl;
    cout << "耗时: " << duration.count() << "ms" << endl;
    
    runTest("高并发压力", true);
}

// 测试7: 真实并发场景下的分片 vs 非分片性能对比
void testRealConcurrencyPerformance() {
    cout << "\n=== 测试7: 真实并发场景性能对比 ===" << endl;
    
    const int capacity = 2000;
    const int testSize = 100000;
    cout << "=== 主缓存总容量: " << capacity << " ===" << endl;
    cout << "=== 缓存操作次数: " << testSize << " ===" << endl;
    cout << "=== 分片数量: 32 ===" << endl;

    const int threadCounts[] = {1, 2, 4, 8}; // 测试不同线程数
    
    cout << "线程数 | 分片耗时(ms) | 非分片耗时(ms) | 性能提升" << endl;
    cout << "-------|--------------|----------------|----------" << endl;
    
    for (int threads : threadCounts) {
        // 测试分片版本
        auto start1 = chrono::high_resolution_clock::now(); // 开始时间
        {
            HashLruKCaches<int, int> shardedCache(capacity, 32, 2); // 32个分片
            
            vector<thread> shardedThreads;
            for (int t = 0; t < threads; ++t) {
                shardedThreads.emplace_back([&, t]() {  // 线程入口函数
                    for (int i = 0; i < testSize; ++i) {
                        int key = (t * testSize + i) % 800; // 不同线程访问不同key范围
                        if (i % 4 == 0) {
                            shardedCache.put(key, i);
                        } else {
                            int value;
                            shardedCache.get(key, value);
                        }
                    }
                });
            }
            for (auto& t : shardedThreads) {
                t.join();
            }
        }
        auto end1 = chrono::high_resolution_clock::now();  // 结束时间
        auto shardedTime = chrono::duration_cast<chrono::milliseconds>(end1 - start1);
        
        // 测试非分片版本
        auto start2 = chrono::high_resolution_clock::now();
        {
            LruKCache<int, int> nonShardedCache(capacity, capacity * 1.5, 2);
            
            vector<thread> nonShardedThreads;
            for (int t = 0; t < threads; ++t) {
                nonShardedThreads.emplace_back([&, t]() {
                    for (int i = 0; i < testSize; ++i) {
                        int key = (t * testSize + i) % 800;
                        if (i % 4 == 0) {
                            nonShardedCache.put(key, i);
                        } else {
                            int value;
                            nonShardedCache.get(key, value);
                        }
                    }
                });
            }
            for (auto& t : nonShardedThreads) {
                t.join();
            }
        }
        auto end2 = chrono::high_resolution_clock::now();
        auto nonShardedTime = chrono::duration_cast<chrono::milliseconds>(end2 - start2);
        
        double improvement = (nonShardedTime.count() - shardedTime.count()) * 100.0 / nonShardedTime.count();
        
        cout << setw(6) << threads << " | "
             << setw(12) << shardedTime.count() << " | "
             << setw(14) << nonShardedTime.count() << " | "
             << fixed << setprecision(1) << setw(8) << improvement << "%" << endl;
    }
}


// 前向声明
void testHotspotWithDistribution(int capacity, int threadCount, int operationsPerThread, const string& distribution);

// 测试8: 热点数据场景下的性能测试
void testHotspotScenario() {
    cout << "\n=== 测试8: 热点数据场景性能测试 ===" << endl;
    
    const int capacity = 1000;
    const int threadCount = 8;
    const int operationsPerThread = 5000;
    
    // 场景1: 均匀分布的热点
    cout << "场景1: 均匀分布热点" << endl;
    testHotspotWithDistribution(capacity, threadCount, operationsPerThread, "uniform");
    
    // 场景2: 集中热点（少数key被频繁访问）
    cout << "\n场景2: 集中热点" << endl;
    testHotspotWithDistribution(capacity, threadCount, operationsPerThread, "concentrated");
}

void testHotspotWithDistribution(int capacity, int threadCount, int operationsPerThread, const string& distribution) {
    atomic<long> shardedSuccess(0);
    atomic<long> nonShardedSuccess(0);
    
    // 分片版本测试
    auto start1 = chrono::high_resolution_clock::now();
    {
        HashLruKCaches<int, int> shardedCache(capacity, 8, 2);
        vector<thread> threads;
        
        for (int t = 0; t < threadCount; ++t) {
            threads.emplace_back([&, t]() {
                random_device rd;
                mt19937 gen(rd());
                uniform_int_distribution<> dis(0, 99);
                
                for (int i = 0; i < operationsPerThread; ++i) {
                    int key;
                    if (distribution == "concentrated") {
                        // 80%的访问集中在20个key上
                        key = (i % 100 < 80) ? (dis(gen) % 20) : (20 + dis(gen) % 80);
                    } else {
                        // 均匀分布
                        key = dis(gen);
                    }
                    
                    int value;
                    if (shardedCache.get(key, value)) {
                        shardedSuccess++;
                    } else {
                        shardedCache.put(key, t * 1000 + i);
                        shardedSuccess++;
                    }
                }
            });
        }
        
        for (auto& t : threads) {
            t.join();
        }
    }
    auto end1 = chrono::high_resolution_clock::now();
    auto shardedTime = chrono::duration_cast<chrono::milliseconds>(end1 - start1);
    
    // 非分片版本测试
    auto start2 = chrono::high_resolution_clock::now();
    {
        LruKCache<int, int> nonShardedCache(capacity, capacity * 1.5, 2);
        vector<thread> threads;
        
        for (int t = 0; t < threadCount; ++t) {
            threads.emplace_back([&, t]() {
                random_device rd;
                mt19937 gen(rd());
                uniform_int_distribution<> dis(0, 99);
                
                for (int i = 0; i < operationsPerThread; ++i) {
                    int key;
                    if (distribution == "concentrated") {
                        key = (i % 100 < 80) ? (dis(gen) % 20) : (20 + dis(gen) % 80);
                    } else {
                        key = dis(gen);
                    }
                    
                    int value;
                    if (nonShardedCache.get(key, value)) {
                        nonShardedSuccess++;
                    } else {
                        nonShardedCache.put(key, t * 1000 + i);
                        nonShardedSuccess++;
                    }
                }
            });
        }
        
        for (auto& t : threads) {
            t.join();
        }
    }
    auto end2 = chrono::high_resolution_clock::now();
    auto nonShardedTime = chrono::duration_cast<chrono::milliseconds>(end2 - start2);
    
    cout << "分片版本 - 成功操作: " << shardedSuccess << ", 耗时: " << shardedTime.count() << "ms" << endl;
    cout << "非分片版本 - 成功操作: " << nonShardedSuccess << ", 耗时: " << nonShardedTime.count() << "ms" << endl;
    cout << "性能提升: " << fixed << setprecision(1) 
         << ((nonShardedTime.count() - shardedTime.count()) * 100.0 / nonShardedTime.count()) << "%" << endl;
}

// 测试9: 锁竞争分析测试
void testLockContentionAnalysis() {
    cout << "\n=== 测试9: 锁竞争分析 ===" << endl;
    
    const int capacity = 2000;
    const int testSize = 100000;
    const int threadCount = 8;
    cout << "=== 主缓存总容量: " << capacity << " ===" << endl;
    cout << "=== 缓存操作次数: " << testSize << " ===" << endl;
    cout << "======  线程数: " << threadCount << " ====== " << endl;
    
    // 测试不同分片数量对性能的影响
    vector<int> shardOptions = {1, 2, 4, 8, 16, 32};
    int bestShardCount = 1;
    long bestTime = LONG_MAX;
    
    cout << "分片数 | 耗时(ms) | 相对性能" << endl;
    cout << "-------|----------|----------" << endl;
    
    for (int shards : shardOptions) {
        auto start = chrono::high_resolution_clock::now();
        
        // 高并发测试
        HashLruKCaches<int, int> cache(capacity, shards, 2);
        vector<thread> threads;
        
        for (int t = 0; t < threadCount; ++t) {
            threads.emplace_back([&, t]() {
                for (int i = 0; i < testSize; ++i) {
                    int key = (t * 131 + i * 37) % 1000; // 产生一定冲突
                    if (i % 3 == 0) {
                        cache.put(key, i);
                    } else {
                        int value;
                        cache.get(key, value);
                    }
                }
            });
        }
        
        for (auto& t : threads) {
            t.join();
        }
        
        auto end = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
        
        // 当前用时，相对于之前最佳用时的提升比例
        double relativePerf = (bestTime * 100.0 / duration.count());
        if (shards == 1) relativePerf = 100.0;

        cout << setw(6) << shards << " | " 
             << setw(8) << duration.count() << " | "
             << fixed << setprecision(1) << setw(8) << relativePerf << "%" << endl;
        
        if (duration.count() < bestTime) {
            bestTime = duration.count();
            bestShardCount = shards;
        }
    }
    
    cout << "最佳分片数: " << bestShardCount << endl;
}


int main() {
    cout << "开始测试 HashLruKCaches..." << endl;
    
    // 基础功能测试
    testBasicFunctionality();
    testShardDistribution();
    testCapacityLimit();
    testPreciseEvictionPolicy();
    
    // 并发性能测试 - 重点测试这些
    testRealConcurrencyPerformance();
    testHotspotScenario();
    testLockContentionAnalysis();
    
    cout << "\n=== 所有测试完成 ===" << endl;
    return 0;
}

// g++ HashLRU_K_Test.cpp